// 给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，在字符串中增加空格来构建一个句子，使得句子中所有的单词都在词典中。返回所有这些可能的句子。

// 说明：

// 分隔时可以重复使用字典中的单词。
// 你可以假设字典中没有重复的单词。
// 示例 1：

// 输入:
// s = "catsanddog"
// wordDict = ["cat", "cats", "and", "sand", "dog"]
// 输出:
// [
//   "cats and dog",
//   "cat sand dog"
// ]
// 示例 2：

// 输入:
// s = "pineapplepenapple"
// wordDict = ["apple", "pen", "applepen", "pine", "pineapple"]
// 输出:
// [
//   "pine apple pen apple",
//   "pineapple pen apple",
//   "pine applepen apple"
// ]
// 解释: 注意你可以重复使用字典中的单词。
// 示例 3：

// 输入:
// s = "catsandog"
// wordDict = ["cats", "dog", "sand", "and", "cat"]
// 输出:
// []

#include <vector>
#include <string>
#include <unordered_map>
#include <iostream>

using std::cout;
using std::endl;
using std::vector;
using std::string;
using std::unordered_map;

class Solution {
public:
    vector<string> wordBreak(string s, vector<string>& wordDict) {
        unordered_map<string, vector<string>> hash{};
        return func(s, wordDict, hash);
    }
    vector<string> func(string s, vector<string>& wordDict, unordered_map<string, vector<string>>& hash) {
        // 如果已经在哈希表中，就直接返回结果
        if (hash.count(s)) return hash[s];
        // 如果s是空字符串，就返回只有一个空字符串的向量
        // 题意不会传进空字符串，但是在递归过程中可能产生空字符串
        if (s.empty()) return {""};
        vector<string> res{};
        for (string word : wordDict) {
            // 对于字典中的每一个word，判断当前单词不在字符串开头，跳过，去判断下一个单词
            if (s.substr(0, word.size()) != word) continue;
            // s.substr(word.size()) 是把当前字符串s开头的word去掉后面剩下的字符串
            vector<string> temp = func(s.substr(word.size()), wordDict, hash);
            for (string str : temp) {
                // 如果str是空的，说明到了结尾，就不用加空格
                cout << str << " ";
                res.push_back(word + (str.empty() ? "" : " ") + str);
            }
            cout << endl;
        }
        // 把当前的结果存入哈希表，并返回
        hash[s] = res;
        return res;
    }
};

int main() {
    Solution slu{};
    string s = "catsanddog";
    vector<string> wordDict = {"cat", "cats", "and", "sand", "dog"};
    vector<string> res = slu.wordBreak(s, wordDict);

    return 0;
}